/*
 * Copyright 2011, 2012 Fabian Wenzelmann
 * 
 * This file is part of Recognition-Procedures-for-Boolean-Functions.
 * 
 * Recognition-Procedures-for-Boolean-Functions is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Recognition-Procedures-for-Boolean-Functions is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Recognition-Procedures-for-Boolean-Functions.  If not, see <http://www.gnu.org/licenses/>.
 */

package de.wenzelmf.booleanFunction.lpb.combinatorial.solver;

import java.util.ArrayList;

import de.wenzelmf.booleanFunction.lpb.combinatorial.splittingTree.SplittingTree;
import de.wenzelmf.booleanFunction.lpb.util.ConversionException;
import de.wenzelmf.booleanFunction.lpb.util.LPB;
import de.wenzelmf.booleanFunction.lpb.util.LPBSummand;
import de.wenzelmf.booleanFunction.util.IntegerValue;
import de.wenzelmf.booleanFunction.util.Tuple;

/**
 * The basic implementation to convert a splitting tree to an LPB.
 * 	
 * Given a {@link CoefficientChooser} and {@link SolverInformation} object it starts in the last
 * column and calls the {@link SplittingTree#handleColumn(int, CoefficientChooser, SolverInformation) handleColumn}
 * of the tree to get the required minimum and maximum values.
 * 
 * Note that this implementation in combination with {@link MinimumChooser} turned out
 * to be incomplete! See the paper by Jan-Georg Smaus, Christian Schilling and Fabian
 * Wenzelmann to the ISAIM 2012
 * (<a href="http://www.cs.uic.edu/pub/Isaim2012/WebPreferences/ISAIM2012_Boolean_Schilling_etal.pdf">here</a>).
 * 
 * It then uses the {@link CoefficientChooser#chooseCoefficient(IntegerValue, IntegerValue, SplittingTree, int)
 * chooseCoefficient} method to get the coefficient.
 * 
 * 
 * @author Fabian Wenzelmann
 * @version 1.0
 */
public class ClassicalTreeSolver implements TreeToLPB
{
	
	/**
	 * The coefficient chooser that is used to choose the coefficients.
	 */
	private CoefficientChooser coeffChooser;
	/**
	 * The solver information that is used to store coefficients, intervals and solve conflicts.
	 */
	private SolverInformation information;
	
	/**
	 * Constructs a new tree solver object.
	 * 
	 * @param coeffChooser The coefficient chooser that is used to choose the coefficients.
	 * @param coefficients The solver information that is used to store coefficients, intervals and solve conflicts.
	 */
	public ClassicalTreeSolver(CoefficientChooser coeffChooser,
			SolverInformation coefficients)
	{
		this.coeffChooser = coeffChooser;
		this.information = coefficients;
	}

	@Override
	public LPB solve(SplittingTree tree) throws ConversionException
	{
		int k = tree.getContext().size() - 1;
		information.init(tree.getContext().size(), tree.getRoot().getDnf(), tree.getContext(), tree);
		while(k >= 0)
		{
			try
			{
				Tuple<IntegerValue, IntegerValue> t = tree.handleColumn(k, coeffChooser, information);
				IntegerValue max, min;
				max = t.getFirst();
				min = t.getSecond();
				if(max != null && min != null)
				{
					// TODO: is this correct with k+1?
					information.setCoefficient(k, coeffChooser.chooseCoefficient(max, min, tree, k + 1));
				}
			}
			catch(CoefficientSelectionException e)
			{
				throw new ConversionException(e);
			}
			k--;
		}
		ArrayList<LPBSummand> summands = new ArrayList<LPBSummand>( tree.getContext().size() - 1 );
		for(int i = 1; i < tree.getContext().size(); i++)
		{
			// TODO: is that correct? it should be...
			summands.add(new LPBSummand(tree.getVariables().getVariable(i - 1), information.getCoefficient(i)));
		}
		Tuple<IntegerValue, IntegerValue> rootInterval = information.getInterval(tree.getRoot());
		return new LPB(summands, chooseDegree(rootInterval));
	}
	
	// TODO: maybe make this method much nicer...
	/**
	 * Tries to choose the degree of the LPB.
	 * 
	 * @param rootInterval The Tuple representing the interval of the root node.
	 * 
	 * @return A valid degree in the interval (s, b] (represented by {@code rootInterval}).
	 * 
	 * @throws ConversionException If the specified interval is empty.
	 */
	protected int chooseDegree(Tuple<IntegerValue, IntegerValue> rootInterval) throws ConversionException
	{
		IntegerValue s, b;
		s = rootInterval.getFirst();
		b = rootInterval.getSecond();
		if(s.isNaN() || b.isNaN())
			throw new ConversionException("Can't choose degree. Minimum and maximum degree. At least one of the numbers is NaN " + this);
		if(s.isNegativeInfinity())
		{
			if(b.isNegativeInfinity())
			{
				throw new ConversionException("Can't choose degree. Minimum and maximum degree: " + this);
			}
			else 
			{
				// TODO: why 0?
				return 0;
			}
		}
		else if(s.isPositiveInfinity())
		{
			throw new ConversionException("Can't choose degree. Minimum and maximum degree: " + this);
		}
		else
		{
			// s is a number
			if(b.isNegativeInfinity())
				throw new ConversionException("Can't choose degree. Minimum and maximum degree: " + this);
			else if(b.isPositiveInfinity())
			{
				return s.intValue() + 1;
			}
			else
			{
				// b is also a number
				int sVal = s.intValue();
				int bVal = b.intValue();
				int smallestSol = sVal + 1;
				if(smallestSol > bVal)
					throw new ConversionException("Can't choose degree. Minimum and maximum degree: " + this);
				else
					return smallestSol;
			}
		}
	}

}
